后面发现这是某次考试的原题来着

怕是太久没打过状压然后连 $k \le 5$ 可能要状压这么明显的提示都给无视了然后就随便敲了个矩阵树骗了 $50$。。。

好所以这题是一道状压

令 $state$ 表示对于 $i$ 点（包括它本身）的前 $k$ 个点的连通状态，$e.g. \{1, 1, 2\}$ 表示 $\{1, 2\}, \{3\}$ 点分别连通

注意为了去重要用最小表示，于是即使当 $k = 5$ 时状态数也不过就 $52$ 个而已了

再令 $f_{i, j}$ 表示前 $i$ 个点且 $i$ 点连通状态为 $j$ 时的方案数，$g_{i, j}$ 表示状态 $i$ 转移到状态 $j$ 时的方案数，则有方程
$$
f_{i, j} = \sum_k f_{i - 1, k} * g_{k, j}
$$
可以发现这就是一个矩阵转移式，故直接矩阵乘法即可

那么至于计算 $g_{i, j}$ 则枚举 $i$，及当前点与前面点的连通状态 $state$（二进制表示），然后并查集维护一下，判断当前 $state$ 是否会与之前冲突（连边后无环且原状态中的最前点（即会被刷掉的点）与当前的 $k$ 个点中至少一个点连边），然后计算出 $j$，最后累加即可

当然要注意考虑 $f$ 矩阵的初始状态，即对于 $i \in [1, k]$，那么计算出里面每个连通块的大小 $a_i$，然后用 $Calley$ 公式 $n^{n - 2}$ 算一下就好了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <cstdio>
#include <cstring>

#define MOD 65521

using namespace std;

typedef long long LL;

const int MAXK = 5 + 10;
const int MAXM = 52 + 10;
const int MAXT = 6e05 + 10;

int K;
LL N;

int allst[MAXM], M = 0; // 压位表示
int mapp[MAXT]= {0};
void DFS (int p, int state, int maxi) {
    if (p == K + 1) {
        allst[++ M] = state;
        mapp[state] = M;
        return ;
    }
    for (int i = 1; i <= min (maxi + 1, K); i ++) {
        int nst = state * 10 + i;
        DFS (p + 1, nst, max (i, maxi));
    }
}

struct Matrix {
    LL a[MAXM][MAXM];

    Matrix () {
        for (int i = 1; i <= M; i ++)
        	for (int j = 1; j <= M; j ++)
        		a[i][j] = 0;
    }
} ;
Matrix operator * (const Matrix& A, const Matrix& B) {
	Matrix ret = Matrix ();
	for (int i = 1; i <= M; i ++)
		for (int j = 1; j <= M; j ++)
			for (int k = 1; k <= M; k ++)
				ret.a[i][j] = (ret.a[i][j] + A.a[i][k] * B.a[k][j] % MOD) % MOD;
	return ret;
}
Matrix f, g;
LL matpower (LL p) {
	while (p) {
		if (p & 1)
			f = f * g;
		g = g * g;
		p >>= 1;
	}
	return f.a[1][1];
}

int father[MAXK];
int find (int x) {
    return father[x] == x ? x : father[x] = find (father[x]);
}
LL power (LL x, int p) {
    if (p < 0) return 1;
    LL cnt = 1;
    while (p) {
        if (p & 1)
            cnt = cnt * x % MOD;
        x = x * x % MOD;
        p >>= 1;
    }
    return cnt;
}
int visit[MAXK]= {0}, bit[MAXK]= {0};
void maintain (int state, int con) {
    for (int i = 1; i <= K + 1; i ++)
        father[i] = i, visit[i] = 0;
    for (int st = state, i = K; i > 0; i --, st /= 10)
        bit[i] = st % 10;
    for (int i = 1; i <= K; i ++)
        for (int j = i + 1; j <= K; j ++) {
            int fx = find (i), fy = find (j);
            if (bit[i] != bit[j] || fx == fy) continue;
            father[fx] = fy;
        }
    for (int j = 1; j <= K; j ++)
        if (con & (1 << (j - 1))) {
            int fx = find (K + 1), fy = find (j);
            if (fx == fy) return ;
            father[fx] = fy;
        }
    bool fail = true;
    for (int i = 2; i <= K + 1; i ++)
        if (find (1) == find (i)) {
            fail = false; break;
        }
    if (fail) return ; // 之前的点都联通
    for (int i = 1; i <= K; i ++)
        bit[i] = find (i + 1);
    int cnt = 0;
    for (int i = 1; i <= K; i ++)
        if (! visit[bit[i]])
            visit[bit[i]] = ++ cnt;
    int final = 0;
    for (int i = 1; i <= K; i ++)
        final = final * 10 + visit[bit[i]];
    g.a[mapp[state]][mapp[final]] ++, g.a[mapp[state]][mapp[final]] %= MOD;
}
int cnt[MAXK]= {0};
void prep () {
    for (int i = 1; i <= M; i ++) { // i in [1, k]
        for (int j = 1; j <= K; j ++) cnt[j] = 0;
        int st = allst[i];
        for (int j = 1; j <= K; j ++, st /= 10)
            cnt[st % 10] ++;
    	LL ret = 1;
    	for (int j = 1; j <= K && cnt[j] > 0; j ++)
    		ret = ret * power (cnt[j], cnt[j] - 2) % MOD;
    	f.a[1][i] = ret;
    }
    int limit = (1 << K) - 1;
    for (int i = 1; i <= M; i ++) // 枚举当前点及其与之前的连通状态
        for (int state = 0; state <= limit; state ++)
            maintain (allst[i], state);
    /*for (int i = 1; i <= M; i ++) {
        for (int j = 1; j <= M; j ++)
            cout << g.a[i][j] << ' ';
        puts ("");
    }*/
}

int main () {
    cin >> K >> N;
    DFS (1, 0, 0), prep ();
    LL ans = matpower (N - K);
    cout << ans << endl;

    return 0;
}

/*
3 5
*/

/*
5 23333333333333
*/